
        <html>
			<head>
			     <title>熵不起得随机数 - 碧云涛</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/tips/1060">http://drops.wooyun.org/tips/1060</a></h1>
				
      <p>
        <h2>0x00 前言</h2>

<hr />

<p>2龙好早以前说，能不能把这篇文章翻了，我拿到文章一看，有点意思，但是很多东西我不清楚，然后在维基百科上看了一些关于Entropy（熵）和PRNG（伪随机生成器）和RNG（随机数生成器）的文章，很拖沓，坑却越挖越大，今天打算跟随原文的过程的说一下这篇文章所说到的事情，但是不是完整的翻译。</p>

<p>直到我看完之后才想起来，这个事情Superhei曾经在Discuz的代码里也提出过：<a href="http://www.80vul.com/dzvul/sodb/14/sodb-2008-14.txt">http://www.80vul.com/dzvul/sodb/14/sodb-2008-14.txt</a>，也是：<a href="http://www.suspekt.org/2008/08/17/mt_srand-and-not-so-random-numbers/">http://www.suspekt.org/2008/08/17/mt_srand-and-not-so-random-numbers/</a>。</p>

<!--more-->

<p>文章里出现一个Entropy（熵），我这里引用一下wikipeida中文的一段话来解释下这个东西。</p>

<p>英语文本数据流的熵比较低，因为英语很容易读懂，也就是说很容易被预测。<strong>即便我们不知道下一段英语文字是什么内容，但是我们能很容易地预测，比如，字母e总是比 字母z多，或者qu字母组合的可能性总是超过q与任何其它字母的组合。</strong>如果未经压缩，一段英文文本的每个字母需要8个比特来编码，但是实际上英文文本的熵 大概只有4.7比特。</p>

<p>接下来是文章，总体来说：能力有限，如存在错误，请多多指出。 注：文章内token,salt,nonce，PRNG,RNG这些缩写我只注了一次，而seed有些地方写成了随机数种子，有些地方写了seed。</p>

<h2>0x01 细节</h2>

<hr />

<p>随机值在PHP中很常见，在框架内或者类库中你都可能看到用它生成的token（令牌），salt（盐值），这些都被当做一种输入放到对应的函数内，随机数很常见很常用。</p>

<p>生成一个范围内的随机数，一个随机的用以加密的密匙，一个不可以被猜测到的可用于验证用户权鉴的字符，生成一个sessionid什么的，我们都会用到随机。</p>

<p>但是这些使用中都存在一个隐患，如果攻击者可以预测你用RNG（随机数生成器）或者PRNG（伪随机数生成器）生成的随机结果会是什么，那他也差不多能知道你最后生成token是什么，或者nonce（一次性验证的凭证）是什么，所以，好的随机数必须是不可以被预测到得随机数。</p>

<p>但是作者认为，在PHP内存在两个关于随机数的弱点：</p>

<pre><code>1，信息泄露。
2，熵池不足。
</code></pre>

<p>信息泄露的意思是，在随机数生成过程中能泄露过程中的一些东西，例如伪随机数种子的值，有了这个随机数的结果也可以更简单的获取到。</p>

<p>熵池不足的意思是，随机数初始的内部状态或者随机数种子的组成的成分就很有限，大概就在一个范围内，PRNG生成的结果也就在一个可能猜到的范围内。</p>

<p>两个对PHP编写的代码来说，都不算好消息。</p>

<h3>什么产生了随机值呢？</h3>

<p>很多人都搞不清楚什么是随机值，可能有些人觉得用unique产生的值和其他随机数比的话，前者更安全一点，后者可能很容易就获取到了，我实际上不认同这个。</p>

<p>关于随机数的讨论应该基于目的，如果你期望使用的随机数是不可被预测的，重要的，那你的随机数就应该不可被预测。</p>

<p>影响随机数的强度的是生成用的熵，熵简单来说是到字节的不确定性，举个例子，我拿出个2进制的字符，它就包含0和1，如果攻击者什么都不知道，好，我们的熵是2，如果攻击者知道结果一定是1，我们的熵就是0比特了，因为能否预测这个需求是和不确定性相反的。</p>

<p>这个在PHP里比较明显，<code>mt_rand</code>生成的随机值永远只是数字，它不输出字符串，特殊字符什么的，所以攻击者只需要尝试数字，如果我们使用<code>/dev/random</code>来生成随机数会比前者的熵池更大。</p>

<p>而且，<code>mt_rand</code>不是真的随机数生成器，它是PRNG（伪随机生成器），采取的是一种被称为梅森旋转的算法，用以生成高质量的伪随机数，它会采用随机数种子来生成随机数的值。</p>

<p>你可以本地测试一下下面的代码</p>

<pre><code>#!php
mt_srand(1361152757.2);

for ($i=1; $i &lt; 25; $i++) {
    echo mt_rand(), PHP_EOL;
}
</code></pre>

<p>产生的随机数看上去是不是很正常，也没什么问题，你再运行一次你会发现结果还是一样的，这不保证在PHP的版本变化后还是如此，但是在过去流行的版本里，是这样的。 如果攻击者可以获取随机数种子，他就可以预测用梅森旋转算法生成的<code>mt_rand</code>的值。 这个特性让随机数种子变成了能否预测的关键。</p>

<h3>在PHP内的随机数</h3>

<p>PHP使用的三种PRNG算法，所以如果攻击者可以获取随机数种子，那么就知道对应算法的结果。</p>

<pre><code>1，线行同余方法 例如：lcg_value
2，梅森旋转算法 例如 mt_rand
3，原生C语言支持的函数 例如rand
</code></pre>

<p>以上实际上在内部函数也复用了，例如array_rand，uniqid，也就是说攻击者如果可以跑一遍所有可能的随机数种子，那么以上所有的值它都可以获取。</p>

<p>为了生成可靠的随机数，PHP也使用外置的熵池，比如<code>openssl_pseudo_random_bytes()</code> 使用Linux系统上的<code>/dev/urandom</code>，或者<code>mcrypt_create_iv()</code>使用了Windows上使用了CSPRNG（Windows密码安全伪随机数生成器），但是这取决于OpenSSL和Mcrypt扩展在PHP里没有开。 <code>/dev/urandom</code>其实也是个PRNG，但是它使用<code>/dev/random</code> 产生高熵池难以预测的种子。</p>

<p>这些告诉我们：</p>

<p>如果需要不被预测的随机数，你的选择是使用<code>openssl_pseudo_random_bytes()</code>，你可以退而设置<code>MCRYPT_DEV_URANDOM</code>使用<code>mcrypt_create_iv()</code>，你也可以直接读<code>/dev/urandom</code>，如果失败了，你也没有别的选择了，你只能反复使用现有的随机数或者密匙进行混合。</p>

<p>理论就是这样，我们来看看我们如何利用知识去实践。</p>

<h3>攻击PHP的RNG</h3>

<p>在实践中，PHP的PRNG都用于各种非常重要的地方。</p>

<p><code>openssl_pseudo_random_bytes()</code>函数只在PHP5.3提供，并且在5.3.4以上的windows上才有，PHP也是在那个版本在Windows上支持<code>mcrypt_create_iv()</code>函数，基于此Windows只支持MCRYPT_RAND影响着rand函数的值，所以5.3之前的有很多应用可能没有较强的随机数生成器。</p>

<p>想想我们在线的服务，使用了下面的代码：</p>

<pre><code>$token = hash('sha512', mt_rand());
</code></pre>

<p>好，一步一步来黑了它。 该脆弱应用的特性： 这不是详细的特性，脆弱特性可以和这份列表有不少出入。</p>

<h4>1. 这个服务器使用mod_php，允许keepalive时多请求被同一个PHP进程处理。</h4>

<p>这是很重要的，每个php进程的种子只会生成一次，如果我们可以对一个PHP进程发送两次请求，PHP会使用同一个种子。</p>

<h4>2. 这个服务器存在CSRF token，密码重置或者者账户确认链接，它们都是使用了mt_rand生成的token。</h4>

<p>为了猜测随机数种子，我们需要一个PHP生成的随机数，无论是mt_rand的结果还是再进行了一下哈希运算，最主要的是要和第二步我们猜测下一个随机数在同一个进程。</p>

<h4>3. 知道一个脆弱的token生成算法</h4>

<p>如果你在攻击一个开源应用你是可以知道这些的，或者收买一个雇员以获取私有的代码，或者前雇员，或者，你自己完全的猜测它的算法，有些token生成算法是简单又粗暴，有可能是mt&#95;rand()或者md5一下mt&#95;rand()，我在这里是假设使用SHA512，接下来我们会看到它也解决不了问题。</p>

<h3>开始攻击</h3>

<p>我们的攻击非常简单，我们要发送两个请求到PHP，服务器会keepalive并且接受第二个请求，接下来我们叫它们为请求A和请求B，获取A请求中的token，比如CSRF token，比如密码重置token，这个token将被严刑拷打，直到它供出它妈是谁，哦，不，它的seed是什么。</p>

<p>B请求更有趣了，让我们提交一个请求去重置管理员的密码，逻辑呢？逻辑是它们是同一个妈生的，哦不，同一个seed生成的(A请求的同一个进程，我们keepalive了）。我们解开A请求里的token的seed的时候，我们就可以用这个seed生成管理员重置密码的链接，并且点击它。</p>

<p>以下条件要在这次攻击里满足：</p>

<pre><code>1，使用请求A去获取一个token，这个token我们可以推出seed的值。
2，使用请求B去拥有一个同样算法生成后放在应用数据库内用以修改密码的的token。
3，破解SHA512获取这个随机数被服务器加密之前的数是什么。
4，使用这个随机数我们去暴力破解出来这个随机数的seed是什么。
5，使用这个seed生成一个用以密码重设的token值。
6，使用我们的密码重设token去重设管理员的密码
7，获取管理员的账户玩一下。
</code></pre>

<p>好，我们开始吧</p>

<p>一步一步的来</p>

<h4>第一步：发起请求A获取token</h4>

<p>我目标的token和密码重设的token都依赖于mt_rand的输出，在我们的例子里，这是一个虚构的应用，它生成的token都是使用统一方案生成的，我们只需要找到CRSF的token并且存在哪里一会儿用。</p>

<h4>第二步：发起请求B获取一个给管理员的密码token</h4>

<p>这个请求就是很简单的提交一个密码重设的表单。这个token会存在数据库里发给用户一个email，这个token要能算出来，如果服务器的特性符合要求，这个请求会和请求A是同一个PHP进程处理的，因此能确认两个请求都使用了mt_rand去调用了同一个随机数种子。</p>

<h4>第三步：破解请求A获取的SHA512后的token的原文</h4>

<p>SHA512开发者们都比较敬畏，因为它是SHA-2家族的算法里目前最大的数字。但是无论如何来说，我们的目标使用它存在一个缺陷 - “随机值都只是数字” （也就是说它的不确定性或者说熵池，太弱了）。如果你去看mt&#95;getrandmax()的返回值，你会发现mt&#95;rand()返回的最大的数字也只是20亿1千4百7十万种组合。这种级别的数字你还是可以暴力破解的。</p>

<p>别这么快就听信我的话。如果你有最近代的低阶GPU。当我打算找出一个hash的值的时候，我选择专业的hashcat-lite。这个版本的hashcat是目前最快的暴力破解的工具之一，你可以在这里下载：<a href="http://hashcat.net/oclhashcat-lite/">http://hashcat.net/oclhashcat-lite/</a></p>

<p>Generate a token using the method I earlier prescribed using the following script: 用下面的脚本生成一个我刚才说到的token：</p>

<pre><code>#!php
$rand = mt_rand();
echo "Random Number: ", $rand, PHP_EOL;
$token = hash('sha512', $rand);
echo "Token: ", $token, PHP_EOL;
</code></pre>

<p>这模仿我们从请求A能获取的那个SHA512后的hash，并且接下来我们把它放在hashcat里跑一下。</p>

<pre><code>./oclHashcat-lite64 -m1700 --pw-min=1 --pw-max=10 -1?d -o ./seed.txt &lt;SHA512 Hash&gt; ?d?d?d?d?d?d?d?d?d?d
</code></pre>

<p>这是所有的参数的意思</p>

<pre><code>-m1700: 定义hash的算法，1700的意思就是SHA512
-pw-min=1 定义hash加密之前的数字的最小的长度
-pw-max=10 定义hash加密之前数字的最大的长度
-1?d 定义我们自定义的字典是仅包含数字
-o ./seed.txt 输出的文件会被重写，别忘了不会有输出在屏幕上。
?d?d?d?d?d?d?d?d?d?d: 表示格式，最长10位，全是数字。
</code></pre>

<p>如果一切顺利，你的GPU也没有爆炸，hashcat几分钟内会找出随机数hash之前的原文是什么，是的，是几分钟，我先前花了一些时间去解释熵池是怎么工作的，然后你现在就可以在练习中明白，<code>mt_rand()</code>产生结果的可能性是如此的少，以至于SHA512加密后我的所有结果我们很短一段时间就计算结束了，使用hash去处理<code>mt_rand</code>的结果几乎没有什么用。</p>

<p>关于hashcat的一些其他用法可以参考之前drops的文章：<a href="http://drops.wooyun.org/tools/655">GPU破解神器Hashcat使用简介</a></p>

<h4>第四步：通过我们获取的随机数去恢复随机数种子</h4>

<p>我们上面说到了，SHA512后的数字解出来只需要几分钟。这会告诉你接下来干什么，通过这个随机数，我们接下来要在跑一个脚本来暴力破解，这个工具叫做php&#95;mt&#95;seed。这是一个小工具，它的作用是取出<code>mt_rand</code>的结果并且暴力破解定位哪些随机数种子会生成那个我们刚才获取的随机数，你可以在<a href="http://download.openwall.net/pub/projects/php_mt_seed/">http://download.openwall.net/pub/projects/php&#95;mt&#95;seed/</a>下载对应的版本，如果出现问题的话，你可以选择一个老一点的版本（最新的版本在我在虚拟环境里测试的时候有些问题）。</p>

<pre><code>./php_mt_seed &lt;对应的随机数&gt;
</code></pre>

<p>这要花比算SHA512要长的时间。它烧的是CPU，不过它会在CPU上尝试任何可能的随机数种子，这将会出现一个或多个随机数种子（也就是这些随机数种子都能产生这个数字）。</p>

<p>在上一步，我们暴力破解获取这个随机数的种子，因为mt&#95;rand调用的种子数不多，这里有另外一个使用python编写的暴力破解mt&#95;rand的工具：<a href="https://github.com/GeorgeArgyros/Snowflake">https://github.com/GeorgeArgyros/Snowflake</a></p>

<h4>第五步：生成可用的token来尝试重置管理员的密码</h4>

<p>Assuming that the total calls to mt_rand() across both Request A and Request B were just two, you can now start predicting the token with the candidate seeds using:</p>

<p>假设在请求A和请求B中调用mt_rand的最大次数是两次，接下来你可以使用我们获取的seed们（有候选的）来预测下一个token是什么。</p>

<pre><code>#!php
function predict($seed) {
    /**
     * Seed the PRNG
     */
    mt_srand($seed);
    /**
     * Skip the Request A call to the function
     */
    mt_rand();
    /**
     * Predict and return the Request B generated token
     */
    $token = hash('sha512', mt_rand());
    return $token;
}
</code></pre>

<p>这个函数会返回对应的seed返回的下一个token。</p>

<h2>0x02 附录</h2>

<hr />

<p>参考资料： 原文： <a href="http://phpsecurity.readthedocs.org/en/latest/Insufficient-Entropy-For-Random-Values.html#mcrypt_create_iv%28%29/dev/random">http://phpsecurity.readthedocs.org/en/latest/Insufficient-Entropy-For-Random-Values.html#mcrypt&#95;create&#95;iv()/dev/random</a></p>

<p>Entropy 熵 <a href="http://en.wikipedia.org/wiki/Entropy">http://en.wikipedia.org/wiki/Entropy</a> <a href="http://zh.wikipedia.org/wiki/%E7%86%B5_%28%E4%BF%A1%E6%81%AF%E8%AE%BA%29">http://zh.wikipedia.org/wiki/%E7%86%B5_%28%E4%BF%A1%E6%81%AF%E8%AE%BA%29</a></p>

<p>梅森旋转算法： <a href="http://en.wikipedia.org/wiki/Mersenne_twister">http://en.wikipedia.org/wiki/Mersenne_twister</a> <a href="http://zh.wikipedia.org/wiki/%E6%A2%85%E6%A3%AE%E6%97%8B%E8%BD%AC%E7%AE%97%E6%B3%95">http://zh.wikipedia.org/wiki/%E6%A2%85%E6%A3%AE%E6%97%8B%E8%BD%AC%E7%AE%97%E6%B3%95</a></p>

<p>PRNG 伪随机数生成器 <a href="http://en.wikipedia.org/wiki/PRNG">http://en.wikipedia.org/wiki/PRNG</a></p>

<p>RNG 随机数生成器 <a href="http://en.wikipedia.org/wiki/Random_number_generator">http://en.wikipedia.org/wiki/Random&#95;number&#95;generator</a> <a href="http://zh.wikipedia.org/wiki/%E9%9A%8F%E6%9C%BA%E6%95%B0%E7%94%9F%E6%88%90%E5%99%A8">http://zh.wikipedia.org/wiki/%E9%9A%8F%E6%9C%BA%E6%95%B0%E7%94%9F%E6%88%90%E5%99%A8</a></p>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          